Communication systems are often used for communicating confidential messages from a sender to a receiver. Optimally, confidentiality is maintained through physical security, i.e., by communicating a confidential message in such a way that no one other than the sender or receiver has access to the message, such as in a sealed, hand-carried package, over a cable, or by means of some other closed communication medium.
Electronic communication media, such as the public telephone network or wireless transmission, have the advantage of speed and convenience. However, these media do not provide physical security. That is, it is possible for a message sent through these communication media to he overheard by parties from whom the content of the message is to be kept secret.
Therefore, a great deal of attention has been given the problem of maintaining a level of secrecy of messages which is comparable to physical security. Much of this attention has manifested itself in encryption technology. Various attributes of a cryptosystem influence how well the system maintains a message in confidence.
In particular, a cryptosystem should not be malleable. The property of malleability is discussed in connection with cryptosystems in Dolev, Dwork, and Naor, "Non-Malleable Cryptography," ACM 089791-397-3/91/004/0542, pp. 542-52 (1991). To be non-malleable, a cryptosystem has two attributes. First, the cryptosystem is semantically secure. That is, if any given information about the plaintext is computable from the ciphertext, then that given information is computable without the ciphertext. Second, given a first ciphertext, it is impossible, or computationally infeasible, to generate a second ciphertext such that the plaintexts corresponding with the first and second ciphertexts are related.
The disadvantage of malleability is illustrated as follow: When a set of related messages are encrypted using an algebraic cryptosystem, the resultant encrypted messages sometimes have a corresponding (not necessarily identical) relationship. For instance, if a set of messages have close numerical values in an ascending numerical series, some malleable encryption keys encrypt the messages into a set of encrypted messages which also have close values in an ascending series. While the message may still be difficult to decrypt, an eavesdropper can still make illicit use of the encrypted message.
For example, consider a contract bidding scenario. Suppose that a municipality has voted to construct a new school, has chosen a design, and advertises that construction companies are invited to bid for the contract by submitting bids encrypted using a malleable public key E. Company A encrypts a bid of $1,500,000 using E, and sends the bid over an insecure line. Company B receives the bid, but cannot decrypt the bid because it does not have the municipality's private decrypting key.
However, given the encrypted Company A bid, Company B may be able to produce a message or its own which, when decrypted using the municipality's decrypting key, results in a bid lower than that of Company A. The cryptosystem is malleable if, given the encrypted bid from Company A, Company B has a likelihood of producing such a message which is greater than its likelihood of doing so would be if Company B did not have the encrypted Company A bid. Company B can thus slightly underbid Company A and win the contract, without necessarily knowing what Company A's bid was, or even what its own decrypted bid will be. Clearly, Company A's interests are served by employing a non-malleable cryptosystem, so that Company B is prevented from generating a bid in this fashion.
This scenario illustrates the difference between physical security, in which Company has no access even to Company A's encrypted bit, and secrecy, produced by encrypting messages. In some contexts, such as this scenario, mere secrecy through the use of a malleable cryptosystem is not a satisfactory substitute for physical security.
A particular area in which secrecy desirably should match physical security is the area of authentication of the source of an encrypted message. Desirably, an authentication scheme should have two attributes. First, the scheme should be secure against attack from an interloper. That is, an interloper should not be able to send a disinformation to a recipient and authenticate the disinformation message as being a valid message sent from a legitimate sender. If no reliable message authentication scheme is in place, then a message received by a recipient R and bearing the source address of a sender S could in fact have been sent by an interloper B. Thus, B could send disinformation about S to R.
The second desirable attribute of an authentication scheme is that it should be possible for the recipient R to convince a third party C that the message was in fact sent from the sender S, and not from an imposter B.
An example of a scenario in which authentication is desirable is a scenario called the "chessmaster attack," or "mafia scam." The name is derived from a chess scenario in which a player simultaneously plays white against one grandmaster and black against another. The player effectively plays the two grandmasters against each other by duplicating the moves made by each grandmaster against the other.
The chessmaster attack is illustrated in a scenario called "Identification: Friend or Foe", or IFF. In one possible IFF scenario, a friendly aircraft F and a friendly ground site G.sub.F communicate, and an enemy aircraft N, with the cooperation of an enemy ground site G.sub.N, seek to communicate disinformation to the friendly aircraft and ground site by impersonating them.
A conventional attempt to establish secure communications is to give the friendly aircraft some secret information s, known only to the friendly ground site. The friendly ground site selects one of a large number of challenges q, and sends q to the friendly aircraft. The friendly aircraft responds with a function F of s and q which is computationally infeasible to calculate without s. Of course, the enemy aircraft may also receive the function. If, later, the friendly ground station challenges the enemy aircraft with a different challenge q', then the required response, a function of s and q', cannot easily be produced, given only q and F(s,q).
However, in a malleable cryptosystem, this communication protocol is subject to attack, using a mafia scam technique. Consider the following sequence of messages, in which the expression following the colon is the message (i.e., a challenge or a response) sent from the first party to the second party:
G.sub.f .fwdarw.N: q PA0 N.fwdarw.G.sub.N : q PA0 G.sub.N .fwdarw.F: q PA0 F.fwdarw.G.sub.N : f(s,q) PA0 G.sub.N .fwdarw.N: f(s,q) PA0 N.fwdarw.G.sub.F : f(s,q)
In this sequence, an enemy plane and ground site, working together, interpose themselves between the friendly ground site and the friendly aircraft, in the manner of a mafia scam. In the fourth step, the Friendly aircraft F provides the enemy ground site with the encrypted response f(s,q). Then, in the sixth step, the enemy aircraft sends the encrypted response to the friendly ground site, thereby responding correctly to the challenge from the friendly ground site.
It is possible for the friendly ground site to decent the enemy's copying by including some special locater information, such as the location of the friendly plane and a time stamp, in the challenge, designated q'. As a result, the enemy plane would need to transmit f(s,q') rather than f(s,q), so mere copying would be insufficient to attack the friendly communication system.
However, the two challenges q and q' are the same, except for the location and the time stamp. In a malleable cryptosystem, f(s,q) and f(s,q') are likely to be similar. Thus, given q, q', and f(s,q), it may be possible for the enemy to obtain f(s,q') and defeat the friendly cryptosystem.
Accordingly, there is a need for a cryptosystem which facilitates the authentication of secret messages, which is not malleable, and therefore not vulnerable to the sort of attacks described above.